package leetcode._06_回溯;

import org.junit.Test;

import java.util.*;

/**
 * @author pppppp
 * @date 2022/3/3 15:16
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 * <p>
 * 示例 1：
 * 输入：nums = [1,1,2]
 * 输出：
 * [[1,1,2],
 * [1,2,1],
 * [2,1,1]]
 * <p>
 * 示例 2：
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */
public class _47_全排列II {

    @Test
    public void T_() {
        // int[] nums = {-1,2,0,-1,1,0,1};
        // int[] nums = {-1,-1,0,0,2};
        // int[] nums = {1,2,2,3};
        // int[] nums = {1,1,2};
        int[] nums = {0,1,0,0,9};
        // List<List<Integer>> lists = permuteUnique(nums);
        List<List<Integer>> lists = permuteUnique_review(nums);
        System.out.println();
    }

    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    // HashSet<List<Integer>> res = new HashSet<>();
    public List<List<Integer>> permuteUnique_review(int[] nums) {
        Arrays.sort(nums);
        ArrayList<Integer> list = new ArrayList<>();
        for (int n : nums) {
            list.add(n);
        }
        dfs_review(0,list);
        return res;
    }

    /*树的同一层 不取重复的值，使用HashSet去重*/
    private void dfs_review(int index, ArrayList<Integer> nums) {
        if(index == nums.size()){
            res.add(new ArrayList<>(nums));
            return;
        }
        HashSet<Integer> set = new HashSet<>();
        for (int i = index; i < nums.size(); i++) {
            if(set.contains(nums.get(i))){
                continue;
            }
            set.add(nums.get(i));
            Collections.swap(nums,index,i);
            dfs_review(index+1,nums);
            Collections.swap(nums,index,i);
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        ArrayList<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }
        dfs(0, list);
        return new ArrayList<>(res);
    }

    private void dfs(int index, ArrayList<Integer> nums) {
        if (index == nums.size()) {
            res.add(new ArrayList<>(nums));
            return;
        }
        for (int i = index; i < nums.size(); i++) {
            /*去除 1/ 1*** 的情况*/
           /* if(i > index && nums.get(i).equals(nums.get(index))){
                continue;
            }*/

            /*去除 1/ 00*** 的情况*/
            if(i > index && nums.get(i).equals(nums.get(i - 1))){
                continue;
            }


            if(i == index || !nums.get(i).equals(nums.get(index))){
                Collections.swap(nums, index, i);
                dfs(index + 1, nums);
                Collections.swap(nums, index, i);
            }
        }
    }

    /*代码随想*/
    //存放结果
    List<List<Integer>> result = new ArrayList<>();
    //暂存结果
    public List<List<Integer>> permuteUnique4(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used, false);
        Arrays.sort(nums);
        backTrack(nums, used);
        return result;
    }

    private void backTrack(int[] nums, boolean[] used) {
        if (path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
            // used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
            // 如果同⼀树层nums[i - 1]使⽤过则直接跳过
            if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
                continue;
            }
            //如果同⼀树⽀nums[i]没使⽤过开始处理
            if (used[i] == false) {
                used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用
                path.add(nums[i]);
                backTrack(nums, used);
                path.removeLast();//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复
                used[i] = false;//回溯
            }
        }
    }


    @Test
    public void T_2() {
        int[] nums = {-1,2,0,-1,1,0,1};
        // int[] nums = {1,1,2};
        List<List<Integer>> lists = permuteUnique4(nums);
        System.out.println();
    }


    /*官方题解*/
    boolean[] vis;
    public List<List<Integer>> permuteUnique2(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }
}
